Slide 35: Key Design Trade-Offs

Property	Sorted Array	Binary Search Tree	Hash Table
Ordering	✓ Yes	✓ Yes	✗ No
Search	O(log n)	O(log n)	O(1) avg
Insert	O(n)	O(log n)	O(1) avg
Delete	O(n)	O(log n)	O(1) avg
Worst-Case	Guaranteed	O(n)	O(n)
Best For	Static ordered data	Dynamic ordered data, range queries	Fast lookups (key-value pairs)

Hover for Details

Hover over a row in the table to see a detailed explanation of that property.

This property determines if the data structure inherently keeps its elements in a sorted sequence.

Arrays & Trees: Keep data sorted, which is essential for operations like finding the minimum/maximum or performing range queries (e.g., "find all users between ages 20 and 30").
Hash Tables: Do not maintain order. They place elements based on a hash function for fast access, sacrificing any sense of sequence.

The efficiency of finding an element.

O(log n): Extremely fast. By repeatedly halving the search space (like in arrays and balanced trees), you can find one item out of a million in about 20 steps.
O(1) average: Even faster! Hash tables compute an element's location directly, taking (on average) just one step regardless of data size.

The efficiency of adding a new element.

O(n) for Arrays: Very slow. To insert an element while maintaining order, you may have to shift every subsequent element one position to the right.
O(log n) for Trees: Fast. It takes logarithmic time to find the correct spot for the new element.
O(1) for Hash Tables: The fastest on average, as it just involves computing the hash and placing the element.

The efficiency of removing an element.

O(n) for Arrays: Very slow, for the same reason as insertion. Removing an element requires shifting all subsequent elements to the left to fill the gap.
O(log n) for Trees: Fast. It involves finding the element and then performing a relatively simple pointer update.
O(1) for Hash Tables: Again, the fastest on average.

The performance guarantee under the least favorable conditions.

Arrays: Performance is predictable and guaranteed. Search is always O(log n).
Unbalanced BSTs: If you insert elements in sorted order, the tree degenerates into a linked list, making all operations a slow O(n).
Hash Tables: If many elements hash to the same slot (a "collision"), lookups in that slot can degrade to O(n) as you search through a list of collided items.

Matching the structure to the problem.

Sorted Array: Ideal when you have a fixed set of data that needs to be searched frequently but rarely updated.
Binary Search Tree: Perfect for when you need to keep a dynamic collection of items sorted, like a database index or the leaderboard in a game.
Hash Table: The go-to for implementing dictionaries, caches, or any scenario where you need extremely fast key-value lookups and don't care about order.